package done.easy_101_200;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

/**
 * 136. Single Number
 * <p>
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。
 * 找出那个只出现了一次的元素。
 * 说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 * <p>
 * 示例 1:
 * 输入: [2,2,1]
 * 输出: 1
 * 示例 2:
 * 输入: [4,1,2,1,2]
 * 输出: 4
 * <p>
 * 由于数字在计算机是以二进制存储的，每位上都是0或1，如果我们把两个相同的数字异或，
 * 0与0异或是0,1与1异或也是0，那么我们会得到0。根据这个特点，我们把数组中所有的数
 * 字都异或起来，则每对相同的数字都会得0，然后最后剩下来的数字就是那个只有1次的数字
 * <p>
 * 2019-03-24 5:22 PM
 **/
@Slf4j
public class SingleNumber {

    @SuppressWarnings("all")
    public int singleNumber(int[] nums) {
        // 190324 first
        return -1;
    }

    @Test
    public void test() {
        int[] nums = new int[]{4, 1, 2, 1, 2};
        log.info("result:{}", singleNumber(nums));
    }
}




























/*
public int singleNumber(int[] nums) {
    int res = 0;
    for (int num : nums) {
        res ^= num;
    }
    return res;
}
*/
